package com.linran.structure_algorithm.数据结构.lesson8_树;

import lombok.Getter;
import lombok.Setter;
import lombok.ToString;

public class ThreadBinaryTreeDemo {

    public static void main(String[] args) {
        //测试一把中序线索二叉树的功能
        ThreadHeroNode root = new ThreadHeroNode(1, "tom");
        ThreadHeroNode node2 = new ThreadHeroNode(3, "jack");
        ThreadHeroNode node3 = new ThreadHeroNode(6, "smith");
        ThreadHeroNode node4 = new ThreadHeroNode(8, "mary");
        ThreadHeroNode node5 = new ThreadHeroNode(10, "king");
        ThreadHeroNode node6 = new ThreadHeroNode(14, "dim");
        //二叉树，后面我们要递归创建，现在简单处理使用手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        // 测试线索化
        ThreadBinaryTree tree = new ThreadBinaryTree();
        tree.setRoot(root);
        // 中序遍历结果
//        tree.infixOrder();
        // 线索化
        tree.threadsNode();

        System.out.println("10号节点的前驱节点是=" + node5.getLeft());
        System.out.println("14号节点的前驱节点是=" + node6.getLeft());
        System.out.println("14号节点的后驱节点是=" + node6.getRight());
        tree.threadList(); // 8 3 10 1 14 6
    }
}

class ThreadBinaryTree {
    private ThreadHeroNode root;
    private ThreadHeroNode pre = null;

    public void setRoot(ThreadHeroNode root) {
        this.root = root;
    }

    public void threadsNode() {
        threadsNode(this.root);
    }

    // 中序线索化二叉树
    public void threadsNode(ThreadHeroNode node) {
        // 左线索化
        if (node.getLeft() != null) {
            threadsNode(node.getLeft());
        }
        // do线索化
        // 左节点指向前驱节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        // 后移
        pre = node;

        // 右线索化
        if (node.getRight() != null) {
            threadsNode(node.getRight());
        }
    }

    //遍历线索化二叉树的一个方法
    // 这里是中序线索化，所以出来的结果是中序遍历
    public void threadList() {
        // 定义一个变量存储当前遍历的节点，从root开始
        ThreadHeroNode node = root;
        while (node != null) {
            // 循环的找到leftType == 1的节点，第一个找到的就是8节点
            // 后面随着遍历二变化，因为当leftType==1时，说明该节点是按照线索化
            // 处理后的有效节点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType() == 1) {
                // 获取当前节点的后继节点
                node = node.getRight();
            }
            // 打印后继节点
            System.out.println(node);
            // 替换这个遍历的节点
            node = node.getRight();
        }
    }
}

@Setter
@Getter
@ToString(exclude = {"left", "right"})
class ThreadHeroNode {
    private int no;
    private String name;
    private ThreadHeroNode left; //默认null
    private ThreadHeroNode right; //默认null
    private ThreadHeroNode pre = null; // 前一个节点

    private int leftType; // 左节点类型 0:左子节点 1:前驱节点,默认0
    private int rightType; // 右节点类型 0:右子节点 1:后继节点,默认0

    public ThreadHeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    // 前序遍历
    public void preOrder() {
        // 输出当前节点
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        //输出当前节点
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    // 后序遍历
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        // 输出当前节点
        System.out.println(this);
    }

    // 前序遍历查找
    public ThreadHeroNode preOrderSearch(int no) {
        System.out.println("前序比较");
        if (this.getNo() == no) {
            return this;
        }
        ThreadHeroNode heroNode = null;
        if (this.getLeft() != null) {
            heroNode = this.getLeft().preOrderSearch(no);
            if (heroNode != null) {
                return heroNode;
            }
        }
        if (this.getRight() != null) {
            heroNode = this.getRight().preOrderSearch(no);
        }
        return heroNode;
    }

    // 中序遍历查找
    public ThreadHeroNode infixOrderSearch(int no) {
        ThreadHeroNode heroNode = null;
        if (this.getLeft() != null) {
            heroNode = this.getLeft().infixOrderSearch(no);
            if (heroNode != null) {
                return heroNode;
            }
        }
        System.out.println("中序比较");
        if (this.getNo() == no) {
            return this;
        }
        if (this.getRight() != null) {
            heroNode = this.getRight().infixOrderSearch(no);
        }
        return heroNode;
    }

    // 后序遍历查找
    public ThreadHeroNode postOrderSearch(int no) {
        ThreadHeroNode heroNode = null;
        if (this.getLeft() != null) {
            heroNode = this.getLeft().postOrderSearch(no);
            if (heroNode != null) {
                return heroNode;
            }
        }
        if (this.getRight() != null) {
            heroNode = this.getRight().postOrderSearch(no);
            if (heroNode != null) {
                return heroNode;
            }
        }
        System.out.println("后序比较");
        if (this.getNo() == no) {
            return this;
        }
        return heroNode;
    }

    public boolean delete(int no) {
        // 当前左子节点判断是否为目标删除节点
        if (this.getLeft() != null && this.getLeft().getNo() == no) {
            this.setLeft(null);
            return true;
        }
        // 当前右子节点判断是否为目标删除节点
        if (this.getRight() != null && this.getRight().getNo() == no) {
            this.setRight(null);
            return true;
        }
        // 左递归删除
        if (this.getLeft() != null && this.getLeft().delete(no)) {
            return true;
        }
        // 右递归删除
        if (this.getRight() != null && this.getRight().delete(no)) {
            return true;
        }
        return false;
    }
}
